import java.util.Arrays;
import java.util.PriorityQueue;

/*
 * @author zzr
 * @date: 2025/10/19  15:37
 * @description:
 */
public class TestHeap {

    private int[] elem;
    private int usedSize;

    public TestHeap() {
        elem = new int[10];
    }

    public void initHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }

    // 创建堆 -- 大根堆
    public void createHeap() {
        for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(parent, usedSize);
        }
    }

    private void shiftDown(int parent, int usedSize) {
        // 左孩子下标
        int child = (parent * 2) + 1;

        while (child < usedSize) { // 确保左孩子不会越界

            // child + 1 找到右孩子下标
            // child + 1 < usedSize 确保右孩子不会越界
            // elem[child] < elem[child + 1] 判断左孩子节点的值是否比右孩子节点的值小
            if (child + 1 < usedSize && elem[child] < elem[child + 1]) {
                // 让 child 一定指向的是左右孩子中较大的节点
                child++;
            }

            // 如果左右孩子中较大的节点的值比父亲节点的值大
            if (elem[child] > elem[parent]) {
                swap(child, parent);
                // 交换完毕后，要处理当前节点的位置
                // 继续向下循环检查，确保震哥哥路径上的所有节点
                // 都满足大根堆的性质
                parent = child;
                child = (parent * 2) + 1;
            } else {
                break; // 已经满足大根堆
            }
        }
    }

    private void swap(int i, int j) {
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }

    public void offer(int val) {
        if (isFull()) {
            elem = Arrays.copyOf(elem, elem.length * 2);
        }
        elem[usedSize] = val;
        shiftUp(usedSize);
        usedSize++;

    }

    private boolean isFull() {
        return elem.length == usedSize;
    }

    // 向上调整的场景是：在堆的末尾插入一个新元素之后，需要让元素上浮到合适的位置
    // 原来的堆已经是有序的了。
    // 所以child 在循环中，只需要和 parent 相比即可~~
    private void shiftUp(int child) {
        // 根据孩子节点的下标找到父亲节点
        int parent = (child - 1) / 2;

        // 当孩子节点不为根节点的时候
        while (child > 0) {
            if (elem[child] > elem[parent]) {
                // 孩子节点的值大于父亲节点的值，不满足大根堆的性质
                // 需要进行调整
                swap(child,parent);
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }

    /**
     * 删除堆的元素
     * 删除堆的元素只能从堆顶开始删除：
     * 1. 将堆顶元素与最后一个元素互换位置
     * 2. usedSize--
     * 3 将堆顶元素向下调整
     * @return
     */
    public int poll() {
        int ret = elem[0];
        swap(0,usedSize - 1);
        usedSize--;
        shiftDown(0,usedSize);
        return ret;
    }

    /*
     * @author zzr
     * @date: 2025/10/19  19:50
     * @description:  利用堆的删除思想来对数组进行排序
     * 先创立一个大根堆，将需要排序的数组放入
     * 然后将堆顶元素与最后一个元素交换位置
     * 重新调整堆为大根堆
     * 继续将堆顶元素与倒数第二个元素交换位置
     * ...
     */
    public void heapSort() {
        int end = usedSize - 1; // 找到最后一个元素索引

        while (end > 0) {
            swap(0,end);
            shiftDown(0, end);
            end--;
        }
    }
}
